package algorithms.question.class06;

import common.util.MyUtil;

/**
 * Nim博弈
 * 给定一个正数数组arr
 * 先手和后手每次可以选择在一个位置拿走若干值，
 * 值要大于0，但是要小于该处的剩余
 * 谁最先拿空arr，谁赢。根据arr，返回谁赢
 *
 * @author guichang
 * @date 2021/8/3
 */

@SuppressWarnings("all")
public class Code5_Nim博弈 {

    public static void main(String[] args) {
        int[] arr = MyUtil.createArray(3, 2, 1);
        MyUtil.print(canWinNim(arr) ? "先手赢" : "后手赢");
    }

    /**
     * 是否先手赢
     */
    public static boolean canWinNim(int[] arr) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        // 异或和为0则后手赢，否则先手赢
        int xor = 0;
        for (int i = 0; i < arr.length; i++) {
            xor ^= arr[i];
        }
        return xor != 0;
    }
}